﻿using System;
using System.Collections.Generic;
using System.Linq;
using Algoritmia.DataStructures.Maps;
using Algoritmia.Utils;

namespace Algoritmia.DataStructures.PriorityMaps
{
    public class FibonacciHeap<TKey,TValue> : IPriorityMap<TKey,TValue>
    {
        private static readonly double Philog = Math.Log((1 + Math.Sqrt(5)) / 2);
        private Node _highestPriorityRoot;
        private int _count;
        private readonly Func<TValue,TValue, bool> _firstHasHigherPriority;
        private readonly IMap<TKey, Node> _map;
        private readonly TValue _highestValuePossible;

        private readonly KeysView<TKey, TValue> _keysView;
        private readonly ItemsView<TKey, TValue> _itemsView;
        private readonly ValuesView<TKey, TValue> _valuesView;

        public FibonacciHeap(TValue highestValuePossible,
                             IEnumerable<KeyValuePair<TKey,TValue>> items = null,
                             Func<TValue,TValue,bool> firstHasHigherPriority = null ,
                             Func<IMap<TKey,Node>> createMap = null)
        {
            _highestValuePossible = highestValuePossible;
            items = items ?? Enumerable.Empty<KeyValuePair<TKey, TValue>>();
            createMap = createMap ?? (() => AlgoritmiaFactory.Maps<TKey, Node>.Default);
            _firstHasHigherPriority = GetPriorityFunction(firstHasHigherPriority);
            _map = createMap() ;
            _highestPriorityRoot = null;

            foreach (var kv in items)
            {
                Add(kv.Key,kv.Value);
            }

            _keysView = new KeysView<TKey, TValue>(this);
            _itemsView = new ItemsView<TKey, TValue>(this);
            _valuesView = new ValuesView<TKey, TValue>(this);
        }

        #region Private Implementation Methods

        private static Func<TValue,TValue, bool> GetPriorityFunction(Func<TValue,TValue, bool> firstHasHigherPriority)
        {
            if (firstHasHigherPriority != null)
            {
                return firstHasHigherPriority;
            }
            if (typeof(TValue).GetInterfaces().Contains(typeof(IComparable<TValue>)))
            {
                return (v1, v2) => Comparer<TValue>.Default.Compare(v1, v2) < 0;
            }
            throw new ArgumentException("No comparison criterium on non comparable data");
        }

        private void RemoveOptimal()
        {
            Node z = _highestPriorityRoot;
            _map.Remove(_highestPriorityRoot.Key);
            if (z != null)
            {
                int nChildren = z.Degree;
                Node child = z.Child;
                while (nChildren > 0)
                {
                    Node nextChild = child.Right;
                    child.Left.Right = child.Right;
                    child.Right.Left = child.Left;
                    child.Left = _highestPriorityRoot;
                    child.Right = _highestPriorityRoot.Right;
                    _highestPriorityRoot.Right = child.Right.Left = child;
                    child.Parent = null;
                    child = nextChild;
                    nChildren--;
                }

                z.Left.Right = z.Right;
                z.Right.Left = z.Left;

                if (z == z.Right)
                {
                    _highestPriorityRoot = null;
                }
                else
                {
                    _highestPriorityRoot = z.Right;
                    Consolidate();
                }
                _count--;
            }

        }

        private void Consolidate()
        {
            Node[] a = new Node[(int)(Math.Log(_count)/Philog)];
            int nRoots = CountRoots();
            Node x = _highestPriorityRoot;
            Node y;

            while (nRoots > 0)
            {
                int d = x.Degree;
                Node next = x.Right;
                while(a[d] != null)
                {
                    y = a[d];
                    if (!_firstHasHigherPriority(x.Value,y.Value))
                    {
                        Node tmp = x;
                        x = y;
                        y = tmp;
                    }
                    Link(y, x);
                    a[d] = null;
                    d++;
                }
                a[d] = x;
                x = next;
                nRoots--;
            }
            _highestPriorityRoot = null;
            foreach (var node in a)
            {
                if (node != null)
                {
                    if ( _highestPriorityRoot != null)
                    {
                        node.Left.Right = node.Right;
                        node.Right.Left = node.Left;
                        node.Left = _highestPriorityRoot;
                        node.Right = _highestPriorityRoot.Right;
                        _highestPriorityRoot.Right = node;
                        node.Right.Left = node;
                        if (_firstHasHigherPriority(node.Value,_highestPriorityRoot.Value))
                        {
                            _highestPriorityRoot = node;
                        }
                    }
                    else
                    {
                        _highestPriorityRoot = node;
                    }
                }
            }
        }

        private void Link(Node y, Node x)
        {
            y.Left.Right = y.Right;
            y.Right.Left = y.Left;
            y.Parent = x;
            if (x.Child == null)
            {
                x.Child = y.Right = y.Left = y;
            }
            else
            {
                y.Left = x.Child;
                y.Right = x.Child.Right;
                x.Child.Right = y.Right.Left = y;
            }
            x.Degree++;
            y.Mark = false;
        }

        private int CountRoots()
        {
            int nRoots = 0;
            Node x = _highestPriorityRoot;
            if ( x != null)
            {
                nRoots++;
                x = x.Right;
                while ( x != _highestPriorityRoot)
                {
                    nRoots++;
                    x = x.Right;
                }
            }
            return nRoots;
        }

        private void ImproveValue(TKey key, TValue value)
        {
            var node = _map[key];
            if (!_firstHasHigherPriority(value,node.Value))
            {
                throw new ArgumentException(String.Format("{0} at {1} does not improve {2}",value,key,node.Value));
            }
            node.Value = value;
            var parent = node.Parent;
            if (parent != null && _firstHasHigherPriority(node.Value,parent.Value))
            {
                Cut(node, parent);
                CascadingCut(parent);
            }
            if (_firstHasHigherPriority(node.Value,_highestPriorityRoot.Value))
            {
                _highestPriorityRoot = node;
            }
            
        }

        private void Cut(Node x, Node y)
        {
            x.Left.Right = x.Right;
            x.Right.Left = x.Left;
            y.Degree--;
            if (y.Child == x)
            {
                y.Child = x.Right;
            }
            if (y.Degree == 0)
            {
                y.Child = null;
            }
            x.Left = _highestPriorityRoot;
            x.Right = _highestPriorityRoot.Right;
            x.Right.Left = x;
            x.Parent = null;
            x.Mark = false;
        }

        private void CascadingCut(Node node)
        {
            var parent = node.Parent;
            if (parent != null)
            {
                if (!node.Mark)
                {
                    node.Mark = true;
                }
                else
                {
                    Cut(node,parent);
                    CascadingCut(parent);
                }
            }
        }

        #endregion 

        #region IPriorityMap<TKey,TValue> Members

        public KeyValuePair<TKey, TValue> GetOptimal()
        {
            if ( _highestPriorityRoot == null)
                throw  new InvalidOperationException("Impossible to get the optimal from an empty FibonacciHeap");
            return new KeyValuePair<TKey, TValue>(_highestPriorityRoot.Key,_highestPriorityRoot.Value);
        }

        public KeyValuePair<TKey, TValue> ExtractOptimal()
        {
            var opt = GetOptimal();
            RemoveOptimal();
            return opt;
        }

        #endregion

        #region IMap<TKey,TValue> Members

        public TValue this[TKey key]
        {
            get { return _map[key].Value; }
            set
            {
                if (_map.Contains(key))
                {
                    ImproveValue(key, value);
                }
                else
                {
                    Add(key, value);
                }
                
            }
        }

        public void Add(TKey key, TValue value)
        {
            Node node = new Node(key, value);
            _map[key] = node;
            if (_highestPriorityRoot == null)
            {
                _highestPriorityRoot = node;
            }
            else
            {
                node.Left = _highestPriorityRoot;
                node.Right = _highestPriorityRoot.Right;
                _highestPriorityRoot.Right =  node.Right.Left = node;

                if ( _firstHasHigherPriority(node.Value,_highestPriorityRoot.Value) )
                {
                    _highestPriorityRoot = node;
                }
            }
            _count++;
        }

        public bool Contains(TKey key)
        {
            return _map.Contains(key);
        }

        public TValue Get(TKey key, TValue defaultValue)
        {
            if (_map.Contains(key))
                return _map[key].Value;
            return defaultValue;
        }

        public ICollectionView<TKey> Keys()
        {
            return _keysView;
        }

        public ICollectionView<KeyValuePair<TKey, TValue>> Items()
        {
            return _itemsView;
        }

        public bool Remove(TKey key)
        {
            if (_map.Contains(key))
            {
                ImproveValue(key, _highestValuePossible);
                RemoveOptimal();
                return true;
            }
            return false;
        }

        public TValue SetDefault(TKey key, TValue defaultValue)
        {
            if (_map.Contains(key))
                return _map[key].Value;
            Add(key,defaultValue);
            return defaultValue;
        }

        public ICollectionView<TValue> Values()
        {
            return _valuesView;
        }

        #endregion

        #region IEnumerable<KeyValuePair<TKey,TValue>> Members

        public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator()
        {
            return _map.Values().Select(value => new KeyValuePair<TKey, TValue>(value.Key,value.Value)).GetEnumerator();
        }

        #endregion

        #region IEnumerable Members

        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }

        #endregion

        #region ICountable Members

        public int Count
        {
            get { return _count; }
        }

        #endregion

        #region Inner Classes

        public class Node
        {
            public Node Parent;
            public Node Child;
            public Node Left;
            public Node Right;
            public TKey Key;
            public TValue Value;
            public int Degree;
            public bool Mark;

            public Node(TKey key, TValue value)
            {
                Key = key;
                Value = value;
                Parent = Child = null;
                Left = Right = this;
                Mark = false;
            }

        }

        #endregion
    }
}
